SecFloat：面向精确浮点计算的安全两方计算

SecFloat: Accurate Floating-Point meets Secure 2-Party Computation

本次介绍Rathee等人发表在 S&P'22 的面向浮点数计算的安全两方计算论文，论文链接如下：(https://eprint.iacr.org/2022/322)

0. Background, Design, & Contribution

0.0 Background

现在大多数的方案在处理浮点数计算的时候采取如下两条技术路线：1）将浮点数计算电路表示为布尔电路，然后利用GC或者GMW协议按比特进行计算；2）将浮点数近似为满足一定精度的定点数，然后利用算术电路和布尔电路混合协议进行数据计算。方法1）会造成巨大的开销，而方案2）则会有一定程度上的精度损失，有些时候这些损失是非常巨大的甚至不可接受。而要保证和浮点数非常接近的精度，虽然可以通过增加比特位长的方式来实现，但是这种方法大约需要512比特的大整数。这无疑给整体开销带来了非常大的负担。

本文面向32比特的单精度浮点数，涉及了安全两方计算（2PC）下的计算库SecFloat。和已有的方案，例如ABY-F和MP-SPDZ相比，SecFloat在精度和开销上都得到了大幅度的提升。SecFloat的主要贡献在于提供了用于浮点数高精度计算的2PC函数。为了达到这个目标，本文对于浮点数的各部分（指数、尾数等）利用并优化了一系列整数下的2PC库。而已有的安全计算方案在精度上不足，而明文精确计算库在2PC下开销巨大（not crypto-friendly），本文的提供的SecFloat在精度和2PC性能二者之间架起了一座桥梁。

0.1 High-Level SecFloat's Design

0.1.1 IEEE Standard & Intel's MKL

IEEE标准中定义的单精度浮点数具有  比特的指数部分和  比特的尾数部分。Intel的数据计算库MKL计算标准数学函数分三步：range reduction, polynomial approximations, output compensation。以 （）为例：

1. range reduction: 首先计算  和  满足 ，其中是整数，；
2. polynomial approximations：对于  利用多项式近似 ；
3. output compensation：计算 。

标准明文库利用高比特位来计算中间值得到精确的计算结果，但是如果直接将该方法迁移到2PC下则会造成巨大的通信和计算开销。

0.1.2 Design of Math Functions

SecFloat也遵循MKL的三步设计计算数学函数，但是出于2PC和明文CPU下计算的性能指标完全不同的考量，SecFloat设计了完全不同的函数以便在2PC下实现高效的函数计算：

1. range reduction: 之前的方案在 比特尾数上利用多项式近似进行rangle reduction，这会带来巨大的开销。本文在满足精度的前提下，使用  比特尾数进行计算，大大减少开销；
2. MKL使用的多项式在2PC下计算开销很大，本文生成了crypto-friendly 分段函数来进行性能优化；
3. 本文提供了一种全新的方法来实现高效安全计算分段函数；
4. 为了进一步提升性能，本文在满足精度的前提下，使用了满足累计误差约束的低精度基本原语算子。

0.1.3 Bitwidth Optimizations

承袭SIRNN的设计思想，本文使用了un-uniform bitwidth技术来优化一些基本原子计算。

0.2 主要贡献

总结一下，SecFloat的主要贡献如下：

1. 高精度的高效2PC计算库，达到了Intel的明文数值计算库的精度要求：SecFloat构造了高精度的精确函数在2PC下实现range reduction, polynimal approximations, 和 output compensation。支持正确的浮点基本原语：加减乘除和比较；提供了精确的数学函数计算，包括三角函数、指数和对数函数。并且支持任意浮点表示；
2. 构造了面向32比特单精度浮点数的SecFloat库，精度比已有方案高6个数量级，效率高3个数量级；
3. 实现了隐私保护下的距离感应测试：该应用对于精度非常敏感，和之前的方案比SecFloat精度提升了4个数量级，并且减少通信 。 本文验证了之前定点数下的安全预测无法满足隐私保护广告推广服务，而SecFloat可以满足这一应用。

1. Premilaries

1.1 Floating-Point Representation

本文关于秘密分享和基本整数计算原语的定义和SIRNN相同，在此不再赘述。对于会单数在本文中的表示，介绍如下： 给定浮点数 ，在浮点数被参数  规定下，表示为四元组 其中：

1. ：如果 , 令 ；
2. ： 的正负性；
3. ：指数部分的有符号表示，取值范围 ；
4. ：正则化的尾数无符号表示，取值范围 ，扩大因子为 （即扩大倍数为 ）。

因此，给定 ，其真实值表示为 。

1.2 Secret Sharing

本文使用SIRNN中的2PC协议构建底层的基本算子，这些基本算子和SIRNN中的相同，具体都展现在表1中。

2. Primitives

本节介绍基本的原语函数。

2.0 Checking for overflows and underflows

如果  上溢出，则设置为 NaN；如果下溢出，则设置为0。具体函数如下：

2.1 Rounding

 对于比特、扩大因子为  的定点数输入 ，返回比特位长为 、扩大因子为 的结果，并且截断结果向偶舍入（rounding-nearest ties to even）。形式化表示为 。函数如下：

对于 ，其中 ，，。首先将  利用TRS替换为比特 （如果 中任意比特为1，则）；进一步，令 。最后用LUT计算  实现向偶取整。

2.2 Round&Check

在浮点计算中，需要将正则化的  比特尾数  从  比特精度减少为  比特精度，因此我们需要舍入  比特，最终结果是  比特。然而，如果 ，那么 则会比 更接近 ，造成溢出。这种情况则需要将  增加 ，并将舍入后的尾数部分设为 。函数如下：

2.3 Multiplication

给定浮点数  和 ，二者的准确乘积 ，其中  且 。具体函数如下：

首先指数部分计算加法，其次尾数部分计算乘法并扩大位长得到具有 比特小数部分的定点数 。然后对于位长进行舍入：

• 如果  是正则化的，则只需要直接舍入  比特；
• 否则需要舍入  比特，并令 。

需要注意的是，如果 ，则第一种情况的舍入结果溢出。因此第一种情况的舍入条件设置为 。最后验证最终的结果是否溢出。

2.4 Addition

给定浮点数  和 ，令  表示二者中绝对值较大的，表示较小的。 首先计算二者指数部分的差距：

• 如果差距过大 ，直接设置结果为 ；
• 否则，左移  以比特，使得二者的指数部分都变为 ，然后根据二者的符号关系对尾数部分进行加法或者减法得到 。

进一步，对  进行归一化操作，即将  左移  比特，其中 。同时，设置扩大因子为 。同时，从  以抵消左移和扩大因子的变化。 最后，调用舍入函数将扩大因子从  降为 。并检查最终结果是否溢出。函数如下：

2.5 Division

给定的分子  和分母 ，得到 ，其中 。其中，指数部分的减法很简单：。对于尾数部分：

• 如果 ，则 ，并令 ；
• 进而计算 

如此，则结果的尾数是正则化的。为了求商，先利用牛顿迭代法近似计算  的倒数，从而得到 。最后的结果需要在  和  中选择，这一步则需要比较  分别到  和  的距离。具体函数如下。

3. Math Functions

本节总结SecFloat对于三角函数、对数和指数函数的计算。为了提升性能，在计算数学函数的时候为了提升性能对于加法和除法做了性能上的优化（cheap addtion and division）。虽然这带来了一定的误差，但是依旧满足精度要求。接下来， 对实数  进行正确舍入之后得到的由参数  定义的浮点数。

3.1 Spline Evaluation

一个段的对于分段函数（splines，or piecewise polynomials），可以用分段点  和  个阶为  的多项式定义。令所有的系数为 ，那么对于 ，可以计算

因此，主要的任务在于对于给定的  从  中选择合适的系数。本文使用的指数部分和尾数部分少量的比特位和  定义  (例如  ) 和 ，其中  对于  满足 当且仅当  时有 。 已有的方法有两种：

• 比较  和 ，根据比较结果选择合适的系数。但是该方法需要次比较；
• 利用LUT将  映射到正确的系数，该LUT一共有  大小，每一项包含  个浮点数参数。由于LUT的开销和表中元素的大小成正比，因此该方法开销也很大。

本文提出的方法如下所示：

LUT  将  映射为 每一项为  比特的one-hot比特向量 。 满足如果  则有 ，否则为 。在提取  之后，则可以通过  计算正确的系数。

从而LUT的每一项和  无关，本文使用的分段函数满足  且 。具体来说，对于tangent函数只需要两个参数，用简单的LUT性能更好；对于指数函数和对数函数，LUT每一项包含6-8个系数，本文的方法能够降低通信 ；和基于比较的方法相比，本文的方法能够比基于比较的方法降低通信 。对于多项式计算，本文使用了Horner's rule优化。

3.2 Sine

对于 ，对于：

• 如果 ，返回  因为输入一定是整数；
• 如果 ，近似为 。

对于其他情况，计算如下：

1）Range Reduction (Step 9-14):

 是奇周期函数，因此可以将  () 归约到计算  ()。令  和  其中 ,  且 。 对于 ，定义

根据 ，有

2) Polynimal Evaluation (Step 15-28):

对于 ，利用  近似；其余的输入范围分为两种情况，我们针对每种情况分别涉及了  的分段函数 (函数形式为 )：

• 如果 ，我们设计了9段的分段函数，其在LUT中用指数部分的低4比特决定；
• 如果 ，我们设计了34段的分段函数 ，指数函数的低2比特和尾数的高5比特可以定位对于的活跃区间（除了，因为区间划分左闭右开）。对于 我们置对应最后一个区间  (Step 24)。

3）Output Compensation (Setp 29)

根据1）中公式，如果 输出 ，否则返回 。具体函数如下。

3.3 Cosine, Tangent, Logarithm, Exponentiation & 2PC Protocols for Floating-Point

其余数学函数的计算遵循和Sine函数相同的构造模板，此部分后续有时间逐步补充。

本文主要列了浮点数相乘、check和 rounding 的具体协议如下，该三个协议都比较简单，对照之前介绍的函数设计即可理解，在这里不再展开。

4. Implementation & Evaluation

首先比较了SecFloat和ABY-F、MP-SPDZ的基本原语性能和精度比较：

进一步是距离感应测试：

最后是面向机器学习广告推荐模型的性能测试：

5. Conclusion

本文设计了面向单精度浮点数的半诚实安全2PC计算库，作者提出接下来面向恶意敌手和64比特浮点数的安全计算库也是一个研究点。

译者简介：

董业， 本科毕业于山东大学计算机科学与技术专业，目前在中国科学院信息工程研究所攻读博士学位。主要研究兴趣包括隐私保护、安全多方计算、同态加密和机器学习。知乎：酸菜鱼。

往期内容：

欢迎投稿

邮箱：[e-mail]

参与更多讨论，请添加小编微信加入交流群